package two_pointer.leetcode_27_easy_two_pointer;

public class RemoveElement {
    public int removeElement(int[] nums, int val) {
        //无效判断
        if(nums == null || nums.length == 0){
            return 0;
        }
        int slow = 0;
        for(int fast = 0; fast < nums.length; fast++){
            /*
                如果nums[fast]值与val相等，就递增fast跳过该元素。
                只要nums[fast] != val，就复制nums[fast] 到 nums[slow]
                [2,3,2] val = 3;
                1. fast = 0 , nums[0] != val --> 复制 [2,3,2]  fast = 1, slow = 1;
                2. nums[1] == val --> 跳过该元素 [2,3,2] fast = 2, slow = 1;
                3. nums[2] != val --> 复制 [2,2,2] fast = 3, slow = 2;
                4. fast 不符合循环条件，循环结束。
                5. 返回slow值， 即 原地 修改了输入数组，返回数组的长度 = 2;  [2,2]
             */
            if(nums[fast] != nums[slow]){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
    /**
     * 考虑当要删除的元素很少时。
     * 比如：[1,2,3,4,5] val = 5, 此时 前4个元素都需要复制一遍。
     * 比如：[4,1,2,3,4] val = 4, 此时 后面四个元素都需要复制一遍。
     *
     * 如何优化这种情况？
     *
     * 注意：只能在要删除的元素很少时。
     *
     * 设置变量i = 0; 当 nums[i] == val时，将当前元素与最后一个位置元素交换，然后将数组长度减小1。
     * 请注意，被交换的最后一个元素可能是您想要移除的值。但是不要担心，在下一次迭代中，我们仍然会检查这个元素。
     */
    public int removeElementSpecial(int[] nums,int val){
        if(nums == null || nums.length == 0){
            return 0;
        }
        int length = nums.length;
        int i = 0;
        while(i < length){
            /*
                考虑这种情况：[3,2,2,3]，当与最后一个元素交换后， [3,2,2] 此时不能将i++，因为被交换的最后一个元素可能是您想要移除的值
             */
            if(nums[i] == val){
                nums[i] = nums[length - 1];
                length--;
            }else {
                i++;
            }
        }
        return length;
    }
}
